#leetcode题目29：除以两个整数
#难度：中等
#时间复杂度：O(logn)
#空间复杂度：O(1)
#
#注意：给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
#返回被除数 dividend 除以除数 divisor 得到的商。
#整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
#示例 1:
#输入: dividend = 10, divisor = 3
#输出: 3
#解释: 10/3 = truncate(3.33333...) = 3



#使用位运算，和减法实现除法

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        flag=-1 if (dividend>0 and divisor<0) or (dividend<0 and divisor>0) else 1
        dividend,divisor=abs(dividend),abs(divisor)
        q,times=0,0
        while dividend>=divisor:
            cur=dividend-(divisor<<times)
            if cur>=0:

                q+=(1<<times)
                times+=1
                dividend=cur

            else:
                times-=1
        return max(-2**31,min(flag*q,2**31-1))
        
        


#测试数据
dividend=10
divisor=3
#预期输出：3
solution=Solution()
print(solution.divide(dividend,divisor))

dividend=-10
divisor=3
#预期输出：-3
solution=Solution()
print(solution.divide(dividend,divisor))


